//
//  85. 最大矩形.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/7.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution85 {
    // 本道题可以转换成矩形的柱状矩行的最大面积
    func maximalRectangle(_ matrix: [[Character]]) -> Int {
        guard matrix.count > 0 else {
            return 0
        }
       
        var matrix2 = Array(repeating: Array(repeating: 0, count: matrix[0].count), count: matrix.count)
        var result = 0
        for i in 0..<matrix.count {
            // 先转换成柱状图
            for j in 0..<matrix[0].count {
                if matrix[i][j] == "1" {
                    matrix2[i][j] = i > 0 ? matrix2[i - 1][j] + 1 : 1
                }
            }
            // 求柱状图矩形面积
            let heights = [0] + matrix2[i] + [0]
            var stack: [Int] = [0]
            for k in 1..<heights.count {
                while heights[k] < heights[stack.last!]  {
                    let height = heights[stack.removeLast()]
                    let width = k - stack.last! - 1
                    result = max(result, height * width)
                }
                stack.append(k)
            }
        }
        return result
    }
    
    static func test() {
        let solution = Solution85()
//        let matrix:[[Character]] = [["1","0","1","0","0"],
//                                    ["1","0","1","1","1"],
//                                    ["1","1","1","1","1"],
//                                    ["1","0","0","1","0"]]
        
//        let matrix:[[Character]]  = []
//        let matrix:[[Character]]  = [["0"]]
//        let matrix:[[Character]] =  [["1"]]
        let matrix:[[Character]] =  [["0","0"]]
        let result = solution.maximalRectangle(matrix)
        print(result)
    }
}
